Knowledge-based or artificial intelligence (hereinafter "AI") computer systems seek to solve problems utilizing computer technology in a manner that would be considered intelligent if performed by a human. In particular, AI computer systems focus on generalized knowledge-representation and search techniques for specialized programs. Knowledge representation involves formulating a problem in a way so that it can be solved. Search techniques involve the ways to efficiently navigate through the knowledge base, i.e., the area of memory where the knowledge is stored, to minimize computation time and memory requirements.
Many of the application systems created with a rule-Express based computer system model are known as expert systems. An expert system is a specialized computer program designed to exhibit the same level of skills as an expert in a specific domain. Expert systems differ from conventional computer systems in that they operate on numeric and symbolic data whereas conventional programs focus on numbers. Expert systems contain explicit knowledge about the domain in which they operate whereas such knowledge is implicit in a program's algorithm in conventional computer systems. Expert systems contain uncertain or inexact relationships, i.e., heuristics, that allow the system to make deductions that are usually correct. Expert systems are coded to contain facts and relationships that are declared explicitly, thus enabling a nonprogrammer to read and understand the knowledge code in the system. Thus, expert systems automate the application of knowledge just as conventional computers automate the application of arithmetic to data processing.
The components of a rule-based expert system are a data store, i.e., the data, a set of production rules, i.e., the program, and an inference engine, i.e., the executor. The data store serves as a global database of symbols representing facts concerning the problem. The set of production rules comprises the program. These rules can be stored in production or rule memory. The inference engine is utilized to fire, i.e., execute, the rules. The inference engine determines which rules are relevant to a given data memory configuration and chooses one or more for execution.
Each rule comprising the set of production rules can have a condition part that describes the data configuration for which the rule is appropriate, commonly referred to as the "left-hand side" and an action part that gives instructions for changing the data configuration, commonly referred to as the "right-hand side". The rules are expressions of conditions that represent empirical associations between patterns of data presented to expert systems and actions that the systems should perform as a consequence. An example of a rule using the rule structure of the OPS5 production-system language is set forth below. For a complete description of OPS5, reference should be made to Brownston et al., Programming Expert Systems in OPS5, (Addison-Wesley Publishing Co., 1985).
______________________________________ (P Rule-Example (patient-data AGE $A HEIGHT ($B &lt; $A) NAME $N) (monitor-data NAME $N PULSE ($C &gt; $B)) ----&gt; (Write "Patient "$N" is in critical condition") ______________________________________
The left-hand side of the rule is represented by two data structures. The first data structure "patient-data" has attributes "AGE" "HEIGHT" and "NAME" that are represented by the variables "$A" "$B" and "$N" respectively. These variables refer to the attributes of a specific patient. The second data structure "monitor-data" has attributes "NAME" and "PULSE" represented by the variables "$N" and "$C", respectively, and also refer to attributes for the same patient referred to in the first data structure. The left-hand side of the above ruleis satisfied when the name attribute has the same value in the patient-data and monitor-data data structure, the patient's height is greater than the patient's age and the patient's pulse rate is greater than the patient's height. If it is determined that the left-hand side of the rule is satisfied, then the right-hand side of the rule can be executed, i.e., the message "Patient "$N" is in critical condition" is written to a printer or a video display terminal.
To avoid testing or retesting every condition in the left-hand side of all the rules each time a new data element is presented to the system, some rule-based expert systems structure the left-hand side of the rules as a "discrimination network" such as a "reticular" network or RETE-net. A RETE-net, with its associated inference engine, will minimize the repetition of tests that have been performed before or that will be performed on subsequent cycles. The RETE-net shares the results of tests among all rules where possible. The RETE-net determines which rules are applicable by only testing those conditions having results that may change in response to a new data element. Also, in a single processor configuration, RETE-nets test conditions that are common to more than one rule only once each time the database changes. Thus, in a single processor configuration, new data is only tested against the successful results of the tests for the old data.
A RETE-net is a data structure that arranges the conditions of all rules as a network of nodes. The patterns which occur in the left-hand side of rules are compiled using known techniques into a network of nodes which test working memory elements for the requisite conditions. To accomplish this, each one of the conditions of the rules is translated into a sequence of tests corresponding to different attributes required by the conditions. Each test of one of the conditions pertaining to a single memory element in the left-hand side of the rule, i.e., A&lt;3, is represented by a one-input node referred to as a "test node". A condition is represented by a single test node even if that condition occurs in the left-hand side of multiple rules. A test pertaining to multiple data elements represented by a chain of test nodes representing a condition, i.e., (A&lt;B) AND (B&lt;C), is joined to the network structure for the preceding part of the rule by a two-input node referred to as a "join node". Each join node corresponds to a logical connector in a rule.
Join nodes maintain lists that record the set of working memory elements received by the node in memory associated with each input of the join node. Join nodes include a pair of memories, one for each of the nodes from which the join nodes receive working memory elements in the form of tokens. These memories are refer to as "beta memory" i.e. the memory associated with an input of the node coupled to a test node representative of a test condition in a rule to the left of the logical connector represented by the join node, and "alpha memory" i.e. the memory associated with an input of the node coupled to a test node representative of a test condition in a rule to the right of the logical connector represented by the join node. The join node may also include tests, e.g., logical AND, which further represent the conditions of the rules. Following the join node may be other join nodes or a node referred to as a terminal node. The terminal node represents the particular rule for the sequence of tests representative of the conditions above coupled to the terminal node.
Typical rule-based expert systems will include a number of rules. A RETE-net in such expert system will have a plurality of test nodes, one for each condition in the rules, so that if the same condition appears in multiple rules, the RETE-net requires only one test node to represent the condition. In addition, join nodes may be shared among rules if the same series of preceding join nodes and test conditions are used in multiple rules.
When working memory elements are added or deleted, they are propagated through the RETE-net in the form of tokens that resemble working memory elements or sequences of working memory elements. The tokens are tagged with a + or - to indicate whether the element or element sequence is being added or deleted. The first step in propagating a working memory element is to pass the token to each test node where each node applies its test. If the test is successful, the node passes a primitive token representative of the working memory element to the successors of the node. If a test is not successful, the match fails and the token is not propagated for further processing. This sequence of passing and testing the token continues until the token reaches a terminal node indicating that the left-hand side of a rule is satisfied and, therefore, a rule is ready to be fired, i.e., executed. The firing of a rule results in the right-hand side of the rule being executed, e.g., the message "Patient "$N" is in critical condition" is written to a printer or a video display terminal.
A rule is ready to be fired once a token has been stored in its corresponding terminal node. Since there may be a plurality of rules, the expert system must follow some procedure for selecting the order for firing rules. This process is referred to as conflict resolution. Conflict resolution must select the order for firing rules because the firing of rules may result in changes to the state of the RETE-net. These changes may cause other rules to be satisfied or satisfied rules to become false. The expert system may utilize conflict resolution to fire all the rules ready to be fired and then reevaluate the RETE-net to ascertain the consequences of the rule firings or conflict resolution may arrange the sequence of firing to depend upon information passed to the expert system.
Traditionally, RETE-nets have not been applied to systems that process real-time data. A real-time system either guarantees a response to a change in critical data within a specific time period, i.e., a hard-real-time system, or simply guarantees a fast response. If there is a change in data, the real-time system must respond to the change by evoking, i.e., starting, a program that processes the data within a certain time period. Often real-time systems will quickly test data to determine if the change is "critical" and will continue with complex processing only in that case. One problem RETE-nets have with real-time data is that it is difficult to predict the amount of time that elapses between the time data is received at the input node of a RETE-net and when a terminal node is ready to fire. Also, RETE-nets respond to any change in data not only "critical" changes in data.
The difficulties set forth above are attributed to the test performed in a join node. A prediction cannot be made as to how long such test will take because the received token must be matched, i.e., compared, to the tokens stored in memory for the join node to ascertain if any matches are found. The number of entries in the join node memory is unknown. Thus, the amount of time required to perform the test with all the stored tokens is unknown. Also, a join node is not designed to only respond to critical data changes. A join node will generate a token if a matched pair of tokens is found regardless of whether the token received represents a change from a noncritical to a critical state or not.
Based on the foregoing, the structure of a RETE-net must be modified to allow an expert system utilizing a RETE-net to respond to critical changes in a real-time environment. Furthermore, the number of tests performed in a RETE-net must be reduced to improve performance. In particular, the RETE-net must discriminate between noncritical and critical data changes and only respond to critical data changes.